package queue.homework;


import java.util.Deque;
import java.util.LinkedList;

/**
 * 这个代码，整体复杂度没有变，po的最差时间复杂度依然是 O(n)的。
 * 但是：平均对与每一个元素来说，都只有一次机会进入stack1，也只有一次机会进入stack2。所以，这样实现，pop的均摊复杂度，变成了O(1)的
 */
public class MyQueue2 {
    private Deque<Integer> stack1;
    private Deque<Integer> stack2;
    int front;

    public MyQueue2() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }

    public int pop() {
        if (!stack2.isEmpty()) return stack2.pop();
        while (stack1.size() > 1) stack2.push(stack1.pop());
        return stack1.pop();
    }

    public void push(int x) {
        if (stack1.isEmpty()) front = x;
        stack1.push(x);
    }

    public int peek() {
        if (!stack2.isEmpty()) return stack2.peek();
        return front;
    }

    public boolean empty() {
        return stack2.isEmpty() && stack1.isEmpty();
    }
}
